package demo1;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;


class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
}


public class Solution {
    TreeNode root = null;
    public TreeNode createTree() {
        TreeNode treeNode1 = new TreeNode(3);
        TreeNode treeNode2 = new TreeNode(5);
        TreeNode treeNode3 = new TreeNode(1);
        TreeNode treeNode4 = new TreeNode(6);
        TreeNode treeNode5 = new TreeNode(2);
        TreeNode treeNode6 = new TreeNode(0);
        TreeNode treeNode7 = new TreeNode(8);
        TreeNode treeNode8 = new TreeNode(7);
        TreeNode treeNode9 = new TreeNode(4);
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;
        treeNode5.left = treeNode8;
        treeNode5.right = treeNode9;
        treeNode3.left = treeNode6;
        treeNode3.right = treeNode7;
        this.root = treeNode1;
        return treeNode1;
    }
    public TreeNode createtree3() {
        TreeNode treeNode1 = new TreeNode(3);
        TreeNode treeNode2 = new TreeNode(9);
        TreeNode treeNode3 = new TreeNode(20);
        TreeNode treeNode4 = new TreeNode(15);
        TreeNode treeNode5 = new TreeNode(7);
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode3.left = treeNode4;
        treeNode3.right = treeNode5;
        return treeNode1;
    }
    public TreeNode p() {
        return root.left;
    }
    public TreeNode q() {
        return root.right;
    }
    //寻找根节点到目标节点的路径
    private boolean getPath1 (TreeNode root, TreeNode p, Stack<TreeNode> stack) {
        TreeNode prev = null;
        while (!stack.isEmpty() || root != null) {
            if (root == p) {
                stack.push(root);
                return true;
            }
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode cur = stack.peek();
                if (cur.right == null || prev == cur.right) {
                    prev = stack.pop();
                } else {
                    root = cur.right;
                }
            }
        }
        return false;
    }
    private boolean getPath (TreeNode root, TreeNode p, Stack<TreeNode> stack) {
        if (root == null){
            return false;
        }
        stack.push(root);
        if (root == p) {
            return true;
        }
        boolean flag = getPath(root.left,p,stack);
        if (flag) {
            return true;
        }
        boolean right = getPath(root.right,p,stack);
        if (right) {
            return true;
        }
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        //获得p的路径
        getPath(root,p,stack1);
        //获得q的路径
        getPath(root,q,stack2);
        int size1 = stack1.size();
        int size2 = stack2.size();
        int size = size1 - size2;
        if (size1 > size2) {
            while (size-- != 0) {
                stack1.pop();
            }
        } else {
            size = -size;
            while (size-- != 0) {
                stack2.pop();
            }
        }
        while (!stack1.empty()) {
            if (stack1.peek() == stack2.peek()) {
                return stack1.peek();
            } else {
                stack1.pop();
                stack2.pop();
            }
        }
        return null;
    }
    //根据前序与在中序遍历构造二叉树
    int i = 0;
    public TreeNode buildTree1(int[] preorder, int[] inorder) {
        return createTree1(0,inorder.length-1,preorder,inorder);
    }
    //找到前序遍历中i下标的值在中序遍历的位置
    private int findIndex(int[] inorder, int[] preorder,int start, int end) {
        for (int j = start; j <= end; j++) {
            if (inorder[j] == preorder[i])
            {
                i++;
                return j;
            }
        }
        return -1;
    }
    private TreeNode createTree1 (int start, int end, int[] preorder, int[] inorder) {
        if (start > end) {
            return null;
        }
        int index = findIndex(inorder, preorder,start,end);
        TreeNode root = new TreeNode(inorder[index]);
        root.left = createTree1(start,index-1,preorder,inorder);
        root.right = createTree1(index+1,end,preorder,inorder);
        return root;
    }

    //中序和后序遍历构造二叉树
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        i = postorder.length - 1;
        return createTree(0,inorder.length-1,inorder,postorder);
    }
    public TreeNode createTree(int start, int end, int[] inorder, int[] postorder) {
        if (start > end) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[i]);
        int index = findIndex(start,end,inorder,postorder);
        if (index == -1) {
            return null;
        }
        root.right = createTree(index+1,end,inorder,postorder);
        root.left = createTree(start,index-1,inorder,postorder);
        return root;
    }
    private int findIndex(int start, int end, int[] inorder, int[] postorder) {
        for (int j = end; j >= start; j--) {
            if (inorder[j] == postorder[i]) {
                i--;
                return j;
            }
        }
        return -1;
    }

    public String tree2str(TreeNode root) {
        if (root == null) {
            return null;
        }
        StringBuilder sb = new StringBuilder();
        treeToString(root,sb);
        return sb.toString();
    }
    public void treeToString(TreeNode t, StringBuilder sb) {
        sb.append(t.val);
        if (t.left != null) {
            sb.append("(");
            treeToString(t.left,sb);
            sb.append(")");
        } else {
            if (t.right != null) {
                sb.append("()");
            } else {
                return;
            }
        }
        if (t.right != null) {
            sb.append("(");
            treeToString(t.right,sb);
            sb.append(")");
        } else {
            return;
        }
    }

    //非递归前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                list.add(root.val);
                root = root.left;
            } else {
                root = stack.pop().right;
            }
        }
        return list;
    }
    //非递归实现中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode cur = stack.pop();
                list.add(cur.val);
                root = cur.right;
            }
        }
        return list;
    }
    //非递归后序遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode cur = stack.peek();
                if (cur.right == null || prev == cur.right) {
                    prev = stack.pop();
                    list.add(prev.val);
                } else {
                    root = cur.right;
                }
            }
        }
        return list;
    }
}












